# 156. 上下翻转二叉树
# https://leetcode-cn.com/problems/binary-tree-upside-down/
# 给你一个二叉树的根节点 root ，请你将此二叉树上下翻转，并返回新的根节点。
#
# 你可以按下面的步骤翻转一棵二叉树：
#
# 原来的左子节点变成新的根节点
# 原来的根节点变成新的右子节点
# 原来的右子节点变成新的左子节点
from typing import Optional
import copy


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    @staticmethod
    def dfs(node: TreeNode, ll: TreeNode, rr: TreeNode):
        assert ll, '左节点不能为None'

        n = copy.deepcopy(node)
        n.left = None
        n.right = None

        left = copy.deepcopy(ll)
        # 右节点没有子节点不需要copy
        right = rr

        # 左节点非叶节点
        if left.left:
            root_, lll, rrr = Solution.dfs(left, left.left, left.right)
            rrr.left = right
            rrr.right = n
            return root_, n, rrr
        else:
            if right:
                right.left = None
                right.right = None
            left.left = right
            left.right = n
            return left, right, n

    def upsideDownBinaryTree2(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root is None:
            return None
        if root.left is None:
            return root
        return solution.dfs(root, root.left, root.right)[0]

    def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root is None:
            return None
        if root.left is None or root.right is None:
            return root

        node_index = {}
        links = []

        def dfs_encode(_root: TreeNode, cnt=-1, max_cnt=-1):
            """
            为每个节点编号并放入links中
            :param _root:
            :param cnt:
            :param max_cnt:
            :return:
            """
            if _root is None:
                return cnt, cnt

            cp = copy.copy(_root)
            cp.left = None
            cp.right = None
            cnt += 1
            max_cnt += 1
            node_index[cnt] = cp

            if _root.left is None:
                # assert _root.right is None, "二叉树左为空右不为空"
                return cnt, max_cnt
            if _root.left:
                idx1, cnt1 = dfs_encode(_root.left, cnt, max_cnt)
                idx2, cnt2 = dfs_encode(_root.right, cnt1, cnt1)
                links.append((cnt, idx1, idx2))
                return cnt, cnt2

        dfs_encode(root)
        parent_map = {}
        for f, l, r in links:
            node_index[l].left = node_index[r]
            node_index[l].right = node_index[f]
            parent_map[r] = l
            parent_map[f] = l

        i = links[0][0]
        while i in parent_map:
            i = parent_map[i]
        return node_index[i]

    @staticmethod
    def get_right(root: TreeNode) -> TreeNode:
        if root.right is None:
            return root
        else:
            print(root.val)
            return Solution.get_right(root.right)


tree = TreeNode(1, left=TreeNode(2, left=TreeNode(4), right=TreeNode(5)), right=TreeNode(3))
tree2 = TreeNode(2, left=TreeNode(4), right=None)
tree3 = TreeNode(1, left=TreeNode(2, left=TreeNode(3, left=TreeNode(4), right=None), right=None), right=None)


solution = Solution()


# res1 = solution.upsideDownBinaryTree2(tree)
# while res1:
#     print(res1.val, res1.left.val if res1.left else None, res1.right.val if res1.right else None)
#     res1 = res1.right
#
# res1 = solution.upsideDownBinaryTree2(tree2)
# while res1:
#     print(res1.val, res1.left.val if res1.left else None, res1.right.val if res1.right else None)
#     res1 = res1.right

res1 = solution.upsideDownBinaryTree2(tree3)
while res1:
    print(res1.val, res1.left.val if res1.left else None, res1.right.val if res1.right else None)
    res1 = res1.right
